\chapter[Podstawowe pojęcia]{Podstawowe pojęcia dotyczące grafów}

\begin{Def}
  \textit{Grafem} $G$ nazywamy parę uporządkowaną $G=(V,E)$, gdzie $V$ jest niepustym zbiorem elementów zwanych wierzchołkami, natomiast $E$ to zbiór krawędzi czyli par nieuporządkowanych $\{v,w\}$, gdzie $v,w \in V$.

  Przez \textit{rząd grafu} rozumieć będziemy jego liczbę wierzchołków czyli $|V|$. Z kolei ilość jego krawędzi $|E|$ będziemy nazywać \textit{rozmiarem grafu}. W Pracy tej omawiane będą jedynie \textit{grafy proste}, czyli takie, w których nie istnieją krawędzie wielokrotne i łączące więrzchołek z samym sobą. Dla uproszczenia krawędzie można również oznaczać krócej $\{v,w\}=vw=wv$. Wierzchołki $v,w$ nazwiemy incydentymi, sąsiednimi lub po prostu sąsiadami jeśli $\{v,w\} \in E$.
% 
%   Zupełnie nieformalnie można powiedzieć że graf jest zbiorem pewnych obiektow połaczonych ze sobą w określony sposób. 
\end{Def}

\begin{Prz}\label{prz1}
  Rozważmy graf $G=(V,E) $, gdzie $ V=\{a,b,c,d,e\}$ oraz $E=\{ab, ac, bc, be, cd\}$
\newline można to przedstawić graficznie:
\end{Prz}
\begin{figure}[!h]\centering\begin{tikzpicture}[scale=0.6]
\tikzstyle{every node}=[inner sep=0pt, minimum size=5pt, draw=black, circle]
	\node(a)[label=180:$a$] at(  0,  0) {};
	\node(b)[label=120:$b$] at(  1,  1) {}
		edge (a);
	\node(c)[label=0:$c$] at(  2,  0) {}
		edge (a) edge (b);
	\node(d)[label=60:$d$] at(2.5,1.5) {}
		edge (c);
	\node(e)[label=$e$] at(1.5,2.5) {}
		edge (b);
\end{tikzpicture}\caption{}\label{rysprosty}\end{figure}
Reprezentacja graficzna nie wpływa na własności grafu, rozmieszczenie wierzchołków na płaszczyźnie może jedynie decydować o czytelności rysunku. Istotne jest jedynie które wierzchołki są ze sobą połączone.

\begin{Def}
  \textit{Stopniem wierzchołka} ${\rm deg}(v)$ nazywać będziemy ilość krawędzi wychodzących z niego czyli: $|\{e \in E : v \in e\}|$. Symbole $\Delta(G)$ oraz $\delta(G)$ oznaczać będą odpowiednio maksymalny i minimalny stopień wierzchołka w grafie $G$.
\end{Def}

\begin{Def}
  \textit{Podgraf} grafu $G=(V,E)$ jest to para $G'=(V',E'),~~V', \subseteq V~~E' \subseteq E$. Czyli inaczej jest to graf jaki można otrzymać z grafu $G$ usuwając z niego pewne wierzchołki i/lub krawędzie.
\end{Def}

\begin{Def}
  Przez \textit{drogę} między wierzchołkami $v$ i $w$ rozumieć będziemy ciąg różnych wierzchołków $(v_1, v_2, \ldots ,v_n)$, taki że $\{v_i,v_{i+1}\} \in E $ dla $i=1,2,\ldots, n-1$.
\end{Def}

\begin{Def}
  Graf $G$ nazywamy \textit{spójnym} jeśli między dowolną parą wierzchołków istnieje droga. Jeśli graf nie jest spójny to jego największe spójne podgrafy nazywamy \textit{składowymi spójnymi}. Przez \textit{rozcięcie} rozumieć będziemy zbiór krawędzi, których usunięcie spowoduje rozspójnienie grafu oraz żaden jego podzbiór nie spełnia tego warunku. Graf nazwiemy \textit{k-spójnym} jeżeli jego minimalne rozcięcię ma moc $k$.
\end{Def}

\begin{Def}
  Przez \textit{graf planarny} rozumieć będziemy graf, który można graficznie przedstawić na płaszczyźnie w taki sposób aby żadne dwie krawędzie nie przecinały się - ich punktami wspólnymi mogą być jedynie wierzchołki, w których się kończą. Przykładowym grafem planarnym jest przedstawiony wyżej graf \ref{rysprosty}.
\end{Def}

\begin{Def}
  Grafy $G_1$ i $G_2$ są \textit{izomorficzne} gdy ich wierzchołki można oznaczyć w taki sposób aby dla każdej pary wierzchołków liczba połączeń między nimi była taka sama w $G_1$ i w $G_2$.
\end{Def}
\begin{Prz}Przykładem izomorficznych grafów są dwa przedstawione poniżej. Jeżeli w grafie po prawej stronie oznaczymy wierzchołki odpowiednio:\newline 
$a\leftrightarrow v_{11},b \leftrightarrow v_{21},c \leftrightarrow v_{12},d \leftrightarrow v_{22},e \leftrightarrow v_{13},f \leftrightarrow v_{23}$
to połączenia między wierzchołkami będą taki same jak w grafie po lewej stronie.
\end{Prz}
\begin{figure}[!h]\centering\begin{tikzpicture}
	\tikzstyle{every node}=[draw, circle, inner sep=0, minimum size=5]
	\foreach \i in {1,2,3}
		\node(g1\i)[label=90:$v_{1\i}$] at(\i,1) {};
	\foreach \i in {1,2,3}
		\node(g2\i)[label=-90:$v_{2\i}$] at(\i,0) {} 
			\foreach \j in {1,2,3} {edge(g1\j) };

	\begin{scope}[shift={(6,0.5)}]
		\foreach \i/\lbl in {1/a,2/c,3/e}
			\node(g1\i)[label={120*(\i-1)}:$\lbl$] at({120*(\i-1)}:1) {};
		\foreach \i/\lbl in {1/b,2/d,3/f}
			\node(g2\i)[label=120*\i-60:$\lbl$] at(120*\i-60:1) {} 
				\foreach \j in {1,2,3} {edge(g1\j) };
	\end{scope}
\end{tikzpicture}\caption{}\label{rys2dzielny}\end{figure}


\begin{Def}
 \textit{Cyklem} nazywać będziemy drogę $(v_1, v_2,\ldots,v_n)$ rozszerzoną o krawędź $(v_1, v_n) \in E$.
\end{Def}

\begin{Def}
  Grafem \textit{k-dzielnym} nazywać będziemy graf, którego zbiór wierzchołków V można podzielić na k podzbiorów $V_1, V_2, \dots, V_k$, takich że żadna para wierzchołków z jednego podzbioru nie jest ze sobą połączona. Przykladowy graf dwudzielny przedstawia rysunek \ref{rys2dzielny}.
\end{Def}

\begin{Def}
  \textit{Graf pełny} $K_n$ jest to graf o n wierzchołkach połączonych ze wszystkimi pozostałymi w $V$. Podgraf bedący izomorficzny z grafem pełnym nazywać będziemy \textit{kliką}.

  \textit{Grafem pełnym k-dzielnym} nazwiemy graf k-dzielny w którym każdy wierzchołek jest połaczony ze wszystkimi wierzchołkami z poza zbioru $V_i$ w którym sie znajduje. Oznaczamy go przez $K_{|V_1|,|V_2|,\ldots,|V_k|}$. Przedstawiony wyżej przykładowy graf dwudzielny jest właśnie grafem $K_{3,3}$
\end{Def}

\begin{Prz}
  \def\n{7}
  Graf pełny o $|V|=\n$.
  \begin{figure}[!h]\centering\begin{tikzpicture}[scale=1.5]
	\tikzstyle{every node}=[draw, circle, inner sep=0, minimum size=5]
	
	\foreach \i in {1,...,\n}
		\node(v\i)[label={(\i-1)*360/\n}:$v_\i$] at({(\i-1)*360/\n}:1) {}
			\foreach \j in {1,...,\i} {
				edge(v\j)
			};
  \end{tikzpicture}\caption{}\end{figure}
\end{Prz}


\begin{Def}
  \textit{Kolorowaniem grafu} nazywamy jednoznaczne przyporządkowanie wierzcholkom, krawędziom lub ścianom pewnych wartości (które można skojarzyć z kolorami) spełniających wytyczne określone przez model kolorowania.
\end{Def}
Ostatnia definicja wiele nam nie mówi bo nie znamy żadnego modelu kolorowania. Nie pozostaje nam więc nic innego, jak zacząć je omawiać w kolejnym rozdziale.